 #define _CRT_SECURE_NO_WARNINGS 1

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        // //解法一：一一比较
        // string ret = strs[0];
        // for(int i = 0; i < strs.size(); i++)
        //     ret = findCommon(ret, strs[i]);

        // return ret;

        //解法二：整体比较
        for (int i = 0; i < strs[0].size(); i++)
        {
            char tmp = strs[0][i];
            for (int j = 1; j < strs.size(); j++)
                if (i == strs[j].size() || tmp != strs[j][i])
                    return strs[0].substr(0, i);
        }

        return strs[0];
    }

    string findCommon(string& s1, string& s2)
    {
        int i = 0;
        while (i < min(s1.size(), s2.size()) && s1[i] == s2[i]) i++;

        return s1.substr(0, i);
    }
};

class Solution {
public:
    string longestPalindrome(string s) {
        //求中心往外扩展
        int begin = 0, len = 0, n = s.size();
        for (int i = 0; i < n; i++)
        {
            //先考虑奇数往外扩展
            int left = i, right = i;
            while (left >= 0 && right < n && s[left] == s[right])
            {
                left--;
                right++;
            }
            if (right - left - 1 > len)
            {
                begin = left + 1;
                len = right - left - 1;
            }

            //再考虑偶数往外扩展
            left = i, right = i + 1;
            while (left >= 0 && right < n && s[left] == s[right])
            {
                left--;
                right++;
            }
            if (right - left - 1 > len)
            {
                begin = left + 1;
                len = right - left - 1;
            }
        }

        return s.substr(begin, len);
    }
};

class Solution {
public:
    string addBinary(string a, string b) {
        string ret;
        int cur1 = a.size() - 1, cur2 = b.size() - 1, t = 0;
        while (cur1 >= 0 || cur2 >= 0 || t)
        {
            if (cur1 >= 0) t += a[cur1--] - '0';
            if (cur2 >= 0) t += b[cur2--] - '0';
            ret += t % 2 + '0';
            t /= 2;
        }
        reverse(ret.begin(), ret.end());
        return ret;
    }
};

class Solution {
public:
    string multiply(string num1, string num2) {
        //1.先将原字符串逆序
        int m = num1.size(), n = num2.size();
        reverse(num1.begin(), num1.end());
        reverse(num2.begin(), num2.end());
        vector<int> tmp(m + n - 1);

        //2.求无进位相加
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                tmp[i + j] += (num1[i] - '0') * (num2[j] - '0');


        //3.将无进位相加进行处理
        string ret;
        int t = 0, cur = 0;
        while (cur < m + n - 1 || t)
        {
            if (cur < m + n - 1) t += tmp[cur++];
            ret += t % 10 + '0';
            t /= 10;
        }

        //4.处理前导零
        while (ret.size() > 1 && ret.back() == '0') ret.pop_back();
        reverse(ret.begin(), ret.end());
        return ret;

    }
};

class Solution {
public:
    string removeDuplicates(string s) {
        string ret;
        for (auto ch : s)
        {
            if (ret.size() && ret.back() == ch) ret.pop_back();
            else ret += ch;//入栈
        }
        return ret;
    }
};